import java.util.Arrays;
import java.util.PriorityQueue;

public class Heap {
    public int[] elem;
    public int useSize;

    public Heap(){
        this.elem = new int[10];

    }

    public void InitArray(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            useSize++;
        }
    }

    public void createHeap(){
        for (int parent = (useSize-1)/2; parent >= 0; parent--) {
            shiftDown(useSize, parent);
        }
    }
    private void shiftDown(int useSize, int parent){
        int child = 2*parent + 1;
        while(child < useSize){
            if(child+1 < useSize && elem[child] < elem[child+1]){
                child++;
            }
            if(elem[parent] <elem[child]){
                swap(elem, parent, child);
                parent = child;
                child = 2*parent + 1;
            }else{
                break;
            }
        }
    }

    private void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //插入
    public void offer(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem, elem.length*2);
        }
        elem[useSize] = val;
        shiftUp(useSize);
        useSize++;
    }

    private void shiftUp(int useSize){
        int child = useSize;
        int parent = (child - 1) / 2;
        while(parent >= 0){
            if(elem[parent] < elem[child]){
                swap(elem, parent, child);
            }else {
                break;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }

    public void poll(){
        if(isEmtpy()){
            return;
        }
        swap(elem, 0, useSize-1);
        useSize--;
        shiftDown(useSize, 0);
    }

    public int peek(){
        return elem[0];
    }

    public boolean isFull(){
        return useSize == elem.length;
    }

    public boolean isEmtpy(){
        return useSize == 0;
    }


//    public int[] smallestK(int[] arr, int k) {
//        PriorityQueue<Integer> qu = new PriorityQueue<>();
//        for(int i = 0; i < arr.length; i++){
//            qu.offer(arr[i]);
//        }
//
//        int[] minNum = new int[k];
//        for(int i = 0; i < k; i++){
//            minNum[i] = qu.poll();
//        }
//        return minNum;
//    }
      public int[] smallestK(int[] arr, int k) {
         int[] ret = new int[k];
         PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());
          for (int i = 0; i < k; i++) {
              maxHeap.offer(arr[i]);
          }

          for (int i = k; i < arr.length; i++) {
              int tmp = maxHeap.peek();
              if(arr[i] < tmp){
                  maxHeap.poll();
                  maxHeap.offer(arr[i]);
              }
          }

          for (int i = 0; i < k; i++) {
              ret[i] = maxHeap.poll();
          }
          return ret;
      }

}
